This background section is intended solely as background information to assist in the understanding of the present disclosure. Nothing in this background section is intended to be an admission of, or to be construed as, prior art against the present disclosure.
The ever-growing demand to transfer confidential information securely over unsecured communication networks has spurred the development of cryptographic technologies such as public key cryptography. According to public key cryptography, each communication is encrypted with one of a pair of keys and decrypted with the other key in the pair. One of the keys, referred to as the “public” key, is easily derived from the other key, referred to as the “private” key, while it is extremely difficult to derive the private key from the public key. Several technologies have been developed to generate these key pairs. One such technology is referred to as “elliptic curve cryptography.”
Elliptic curve cryptography (ECC) has become a vital technology because it offers the highest security per bit of any known public key cryptosystem. ECC is described in V. S. Miller, “Use of elliptic curves in cryptography,” in Proc. Adv. Cryptolog. (Crypto '85), 1986, pp. 417-426; and N. Koblitz, “Elliptic curve cryptosystems,” Math. Computations, vol. 48, pp. 203-209, 1987. The core computation in an ECC processor is the point multiplication which calculates k×P0 for a point P0 on the elliptic curve and an integer k. Detailed arithmetic descriptions can be found in A. J. Menezes, “Elliptic curve public key cryptosystems”, Norwell, Mass.: Kluwer Academic, 1993 and M. Rosing, “Implementing Elliptic Curve Cryptography”, Greenwich, Conn.: Manning, 1998. Tremendous research efforts have been devoted to developing efficient hardware and/or firmware implementations of the ECC processor. Examples are given in G. Agnew, R. Mullin, I. Onyszchuk and S. Vanstone, “An implementation of elliptic curve cryptosystems over F2155,” IEEE J. Selected Areas Communications, vol. 11, pp. 804-813, June 1993; S. Sutikno, A. Surya, and R. Effendi, “An implementation of ElGamal Elliptic Curve Cryptosystems,” Proc. 1998 IEEE Asian Pacific Conf. Circuits and Systems (APCCAS '98), pp. 483-486, November 1998; G. Orlando and C. Paar, “A High-Performance Reconfigurable Elliptic Curve Processor for GF(2m),” Proc. Cryptographic Hardware and Embedded Systems (CHES 2000), pp. 41-56, August 2000; S. Xu and L. Batina, “Efficient Implementation of Elliptic Curve Cryptosystems on an ARM7 with Hardware Accelerator,” Proc. Information Security (ISC 2001), pp. 266-3279, October 2001; and T. IZU and T. Takagi, “Fast Elliptic Curve Multiplications Resistant against Side Channel Attacks.”
The ECC operations can be conducted in either binary field or prime field. The binary field GF(2n) ECC is suitable for fast and compact hardware compared with a prime field GF(p) ECC because there is no carry propagation for addition in a binary field. However, the prime field ECC is preferred in communication applications because of its higher security. Prior implementations have the disadvantages of high complexity and low throughput because they are designed for a general prime modulus, such as the Montgomery modular multiplier-based ECC processor, which is described in P. L. Montgomery, “Modular multiplication without trial division,” Mathematics of Computation, 44(170):519-521, April 1995.